home *** CD-ROM | disk | FTP | other *** search
/ Amiga Plus 2000 #4 / Amiga Plus CD - 2000 - No. 4.iso / Tools / Dev / bignum / bignum1.c < prev    next >
Encoding:
C/C++ Source or Header  |  2000-05-29  |  5.9 KB  |  207 lines
  1. /* +++Date last modified: 05-Jul-1997 */
  2.  
  3. /* BIGNUM1.C
  4. **
  5. ** Routines to do Big Number Arithmetic. These are multi-precision, unsigned
  6. ** natural numbers (0, 1, 2, ...). For the storage method, see the BigNum
  7. ** typedef in file BIGNUM.H
  8. **
  9. ** Released to the public domain by Clifford Rhodes, June 15, 1995, with
  10. ** no guarantees of any sort as to accuracy or fitness of use.
  11. */
  12.  
  13. #include <stdlib.h>
  14. #include "bignum.h"    /* Typedef for BigNum type */
  15.  
  16.  
  17. BigNum * BigNumAdd(const BigNum * a, const BigNum * b)
  18. {
  19.       /* Big Numbers a and b are added. If successful a pointer to the sum is
  20.       ** returned. If unsuccessful, a NULL is returned.
  21.       ** Neither a nor b is changed by the call.
  22.       */
  23.  
  24.       UShort  carry = 0;
  25.       int     size, la, lb;
  26.       long    tsum;
  27.       BigNum  * sum;
  28.  
  29.       /* Allocate memory for Big Number sum to be returned... */
  30.  
  31.       size = max(a->nlen, b->nlen) + 1;
  32.       if ((sum = BigNumAlloc(size)) == NULL)
  33.             return NULL;
  34.  
  35.       /* Get indexes to last digits in each number (Least significant) */
  36.  
  37.       la = a->nlen - 1;
  38.       lb = b->nlen - 1;
  39.       size--;
  40.  
  41.       while (la >= 0 && lb >= 0)    /* While both a and b have data */
  42.       {
  43.             tsum = carry + (long) *(a->n + la) + (long) *(b->n + lb);
  44.             *(sum->n + size) = (UShort) (tsum % (long) MODULUS);
  45.             carry = (tsum / (long) MODULUS) ? 1 : 0;
  46.             la--;
  47.             lb--;
  48.             size--;
  49.       }
  50.       if (lb < 0)                   /* Must see if a still has data */
  51.       {
  52.             while (carry && la >= 0)
  53.             {
  54.                   tsum = carry + (long) *(a->n + la);
  55.                   *(sum->n + size) = (UShort) (tsum % (long) MODULUS);
  56.                   carry = (tsum / (long) MODULUS) ? 1 : 0;
  57.                   la--;
  58.                   size--;
  59.             }
  60.             while (la >= 0)
  61.             {
  62.                   *(sum->n + size) = *(a->n + la);
  63.                   la--;
  64.                   size--;
  65.             }
  66.       }
  67.       else                          /* See if b still has data */
  68.       {
  69.             while (carry && lb >= 0)
  70.             {
  71.                   tsum = carry + (long) *(b->n + lb);
  72.                   *(sum->n + size) = (UShort) (tsum % (long) MODULUS);
  73.                   carry = (tsum / (long) MODULUS) ? 1 : 0;
  74.                   lb--;
  75.                   size--;
  76.             }
  77.             while (lb >= 0)
  78.             {
  79.                   *(sum->n + size) = *(b->n + lb);
  80.                   lb--;
  81.                   size--;
  82.             }
  83.       }
  84.       *(sum->n + size) = carry;
  85.  
  86.       return sum;
  87. }
  88.  
  89. BigNum * BigNumSub(const BigNum * a, const BigNum * b)
  90. {
  91.       /* Big Numbers a and b are subtracted. a must be >= to b. A pointer to
  92.       ** the difference (a - b) is returned if successful. If unsuccessful,
  93.       ** a NULL is returned.
  94.       ** Neither a nor b is changed by the call.
  95.       */
  96.  
  97.       int      size, la, lb, borrow = 0;
  98.       long     tdiff;
  99.       BigNum * diff;
  100.  
  101.       /* Allocate memory for Big Number difference to be returned... */
  102.  
  103.       if ((diff = BigNumAlloc(a->nlen)) == NULL)
  104.             return NULL;
  105.  
  106.       la = a->nlen - 1;
  107.       size = la;
  108.       lb = b->nlen - 1;
  109.  
  110.       while (lb >= 0)
  111.       {
  112.             tdiff = (long) *(a->n + la) - (long) *(b->n + lb) - borrow;
  113.             if (tdiff < 0)
  114.             {
  115.                   tdiff += (long) (MODULUS - 1);
  116.                   borrow = 1;
  117.             }
  118.             else  borrow = 0;
  119.             *(diff->n + size) = (UShort) tdiff + borrow;
  120.             la--;
  121.             lb--;
  122.             size--;
  123.       }
  124.       while (la >= 0)          /* Must get rest of a->n */
  125.       {
  126.             tdiff = (long) *(a->n + la) - borrow;
  127.             if (tdiff < 0)
  128.             {
  129.                   tdiff += (long) (MODULUS - 1);
  130.                   borrow = 1;
  131.             }
  132.             else  borrow = 0;
  133.             *(diff->n + size) = (UShort) tdiff + borrow;
  134.             la--;
  135.             size--;
  136.       }
  137.       if (borrow)   /* We've got an underflow here! */
  138.       {
  139.             BigNumFree(diff);
  140.             return NULL;
  141.       }
  142.       return diff;
  143. }
  144.  
  145. BigNum * BigNumMul(const BigNum * a, const BigNum * b)
  146. {
  147.       /* Big Numbers a and b are multiplied. A pointer to the product
  148.       ** is returned if successful. If unsuccessful, a NULL is returned.
  149.       ** Neither a nor b is changed by the call.
  150.       */
  151.  
  152.       int      size, la, lb, apos, bpos, ppos;
  153.       UShort   carry;
  154.       BigNum * product;
  155.  
  156.       /* Allocate memory for Big Number product to be returned... */
  157.  
  158.       size = a->nlen + b->nlen;
  159.       if ((product = BigNumAlloc(size)) == NULL)
  160.             return NULL;
  161.  
  162.       la = a->nlen - 1;
  163.       lb = b->nlen - 1;
  164.       size--;
  165.  
  166.       bpos = lb;
  167.  
  168.       while (bpos >= 0)             /* We'll multiply by each digit in b */
  169.       {
  170.             ppos = size + (bpos - lb);    /* Position in product */
  171.  
  172.             if (*(b->n + bpos) == 0) /* If zero multiplier, skip this pass */
  173.                   ppos = ppos - la - 1;
  174.             else                    /* Multiply a by next b digit */
  175.             {
  176.                   apos = la;
  177.                   carry = 0;
  178.                   while (apos >= 0) /* Go a digit at a time through a */
  179.                   {
  180.                         ULong temp;
  181.  
  182.                         temp = (ULong) *(a->n + apos) *
  183.                               (ULong) *(b->n + bpos) + carry;
  184.  
  185.                         /*
  186.                         ** We must add any previous product term in
  187.                         ** this 'column' too
  188.                         */
  189.  
  190.                         temp += (ULong) *(product->n + ppos);
  191.  
  192.                         /* Now update product term, remembering any carry */
  193.  
  194.                         *(product->n + ppos) =
  195.                               (UShort) (temp % (ULong) MODULUS);
  196.                         carry = (UShort) (temp / (ULong) MODULUS);
  197.  
  198.                         apos--;
  199.                         ppos--;
  200.                   }
  201.                   *(product->n + ppos) = carry;
  202.             }
  203.             bpos--;
  204.       }
  205.       return product;
  206. }
  207.